package leetcodeHis;

/**
 * 两数之和
 */
public class twoSum {
    public static void main(String[] args) {
        //数组实现两数相加
        int[] arr = {2,7,11,15};
        int target = 9;
        int[] re = twoSum(arr, target);
        System.out.println(re[0] + "," +re[1] );

        //链表实现两数相加
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);
        ListNode l = addTwoNumbers(l1, l2);
        while(l!=null) {
            System.out.println(l.val);
            l = l.next;
        }

    }

    //两数之和暴力版本
    public static int[] twoSum(int[] nums, int target) {
        int[] re = new int[2];
        if(nums.length>0) {
            for(int i=0;i<nums.length;i++) {
                for(int j=i+1;j<nums.length;j++) {
                    if(nums[i] + nums[j] == target) {
                        re[0] = i;
                        re[1] = j;
                    }
                }
            }
        }
        return re;
    }

    /**
     * 链表实现两个数相加,两个非负数反向用链表表示  342 + 465 = 807      2——>4——>3    5——>6——>4
     * !!!超时了
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode re = new ListNode(-1);
        ListNode head  = re;
        int level = 0;
        while(l1!=null || l2!= null) {
            int x = l1==null? 0 : l1.val;
            int y = l2==null? 0 : l2.val;
            if(x != 0) {l1 = l1.next;}
            if(y != 0) {l2 = l2.next;}
            int sum = x + y ;
            re.next = new ListNode(sum%10+level);
            level = sum>=10 ? 1 : 0;
            re = re.next;
        }
        return head.next;
    }
}
